import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class GetPermutation {

    private PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    public String getPermutation1(int n, int k) {
        boolean[] flag = new boolean[n];
        process(0, n, k, flag, 0);
        return heap.peek().toString();
    }

    public void process(int i, int n, int k, boolean[] flag, int sum) {
        if (heap.size() == k) return;
        if (i == n) {
            if (heap.size() < k) {
                heap.offer(sum);
            }
            return;
        }
        for (int j = 0; j < n; j++) {
            if (!flag[j]) {
                sum = sum * 10 + j + 1;
                flag[j] = true;
                process(i + 1, n, k, flag, sum);
                sum = (sum - j - 1) / 10;
                flag[j] = false;
            }
        }
    }

    public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
        factorials[0] = 1;
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            factorials[i] = factorials[i - 1] * i;
            list.add(i);
        }
        list.add(n);
        k -= 1;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int index = k / factorials[n - i];
            stringBuilder.append(list.remove(index));
            k -= index * factorials[n - i];
        }
        return stringBuilder.toString();
    }
}
